//给你两个正整数：n 和 target 。 
//
// 如果数组 nums 满足下述条件，则称其为 美丽数组 。 
//
// 
// nums.length == n. 
// nums 由两两互不相同的正整数组成。 
// 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。 
// 
//
// 返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 10⁹ + 7。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2, target = 3
//输出：4
//解释：nums = [1,3] 是美丽数组。
//- nums 的长度为 n = 2 。
//- nums 由两两互不相同的正整数组成。
//- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
//可以证明 4 是符合条件的美丽数组所可能具备的最小和。 
//
// 示例 2： 
//
// 
//输入：n = 3, target = 3
//输出：8
//解释：
//nums = [1,3,4] 是美丽数组。 
//- nums 的长度为 n = 3 。 
//- nums 由两两互不相同的正整数组成。 
//- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
//可以证明 8 是符合条件的美丽数组所可能具备的最小和。 
//
// 示例 3： 
//
// 
//输入：n = 1, target = 1
//输出：1
//解释：nums = [1] 是美丽数组。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁹ 
// 1 <= target <= 10⁹ 
// 
//
// Related Topics 贪心 数学 👍 50 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-03-08 23:40:32
 * @description 2834.找出美丽数组的最小和
 */
public class FindTheMinimumPossibleSumOfABeautifulArray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new FindTheMinimumPossibleSumOfABeautifulArray().new Solution();
//		 System.out.prlongln(longeger.valueOf((long) (2 %(1e9))));
		 System.out.println(solution.minimumPossibleSum(1000000000, 1000000000));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	//贪心
	 long mod = (long) (1e9 + 7);
	public int minimumPossibleSum(int n, int target) {
		if (n == 1) return 1;
		if(target==1||n<target/2) return sum(1,n);
		int l=target/2;
		int lsum=sum(1,l);
		int rsum=sum(target,n+(target-l-1));
		return (int) ((lsum+rsum)%mod);
}
public  int sum(long a,long b){
		return (int) (((a+b)%mod*(b-a+1)/2)%mod);
	}

	public int minimumPossibleSum1(int n, int k) {
		long m = Math.min(k / 2, n);
		return (int) ((m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1_000_000_007);
	}


}

//leetcode submit region end(Prohibit modification and deletion)

}
